Re: Assembler: Forward ref. label

<<... a 2-pass assembler, 1st pass generate label address and 2nd pass
generate final code.>>


which
<< ... allow(s) label to appear in expression, and this cause a problem. If the
expression conatins label computaion, and the result will not
be determined until 2nd pass, I select one-word instruction or two-word by the
expression result. >>
...
<< Thats mean I cannot generate correct machine code and label
address in 1st pass. >>


I know what you mean when you say "correct". You mean that you can
not generate the best code (as in smallest). It is important that you
can generate the correct code by always generating the larger
instruction, or accepting this fate after certain minimum economic
checks.


First the problem happens most severely when the label computations
involve forward references. When you have backward regerences there is
less severe of a problem because you might know enough
immediately. But if you don't have clear enough information in the
back references and in the case of forward references, the basic
question becomes how much is it worth to resolve the matter.


A technique called backpatching relates to this situation. Generally
it can even be used on a 1-pass parser, and can be used within a
single pass of even a multi-pass parser.


In effect you make a list of unresolved address issues (like minimum
size of a compile time label computation results). At the end of the
pass you review this list. (you can place back referenced label
uncertainties onto this list also).


A few basic possibilities can occur with the size you mentioned
interest in: a) the target labels are within the 128 byte size limit,
b) target computations are over but close to the limit and have
content that might shrink during this analysis, c) target sizes are
way over and either cannot shrink enough, have no shrinkable content,
or they are not worth trying to shrink relative to the payback for the
current item(s) that you hope to optimize.


Your choice at the end of this first crude analysis is whether there
is enough payback to motivate you to make this seriously recursive.
The shrinking of the individual instructions then shrinks the block(s)
which could impact the label computations you have just analyzed. Any
computation that was not shrunk (and not excluded as impossible to
shrink) is open for further analysis.


It is possible to make this shrinking actually recursive, but then
there is a need to prevent loops (wherein two or more shrinkable
references refer to eachothers label domain). It is better to make
this kind of routine simply iterative if you think there is value in
anything more than the first reduction.


This technique requires that you hold the code in an intermediate form
(triples or quadruples) that you can backpatch.


However, it is not unusual for this kind of optimization to be left
out of the front-end when the design involves intermediate code that
can be optimized in other ways as well.


Backpatching applies to a single pass but is actually a kind of
miniature additional pass, dealing only with instructions on a limited
list (trying to fix them up). Since implementors can make the
backpatching iterative or even recursive, a lot can be revisted and it
can cost a lot of time. So there is always a legitimate question as to
how much it is worth.


Where the instruction set will permit it, it is sometimes sufficient
to shrink only the specific instructions, and fill the next space with
a NOP. This avoids having an impact on ANY preceding label
computation.


On DOS machines this can actually be done with .EXE files after link!
(for jump instructions, I have not seen it for " MOV ax, literal ", as
in your posted example).


There is a good presentation of backpatching in "Compilers,
Principles, Techniques, and Tools", Aho, Sethi, Ullman
(Addison-Wesley).


Best Wishes,


Robert Rayhawk
RKRayhawk@aol.com

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