Re: Assembler: Forward ref. label

Our moderator wrote:
> [This is similar to the variable length branch problem. To get correct
> code, you need an intermediate pass between your 1st and second passes.
> In the first pass, assume it's all two-word code and remember the places
> you might have to adjust, then at the end of pass 1 go through and see
> which ones can actually be short, rippling up all the symbols after each
> code shrink, and repeat until you don't find any more. This isn't quite
> optimal (it's apparently an NP complete problem) but it's close enough
> and not hard to implement. There was an article in the CACM by Szymanski
> about 20 years ago that explained this in detail. -John]


To solve the variable length branch problem one can start with the
pessimistic assumption that all branches are long, and reduce those
which can be shortened until a fix-point is reached. This approach
will not always give you the optimal (shortest program) solution.


1: beq.l 2
``some code''
bne.l 1
2:


``Some code'' together with a short branch is short enough to be
spanned by a short branch, but too long if it is combined with a long
branch. The best solution -- using two short branches -- will not be
found, as none of the two branches alone can be shortened.


Starting with the optimistic assumption that all branches can be
short, and just elongating those which must be longer, until a
fix-point is reached will find the optimal solution.


Starting with the optimistic assumption will only result in a legal
program when the fix-point is actually reached, whereas the pessimistic
approach can be interrupted at any time and the result will be a legal
program. In practice however, the pessimistic approach is quite fast.
A simple implementation will reach the fix-point in O(l*b^2) time,
where `b' is the number of branches, and `l' the number of different
branch-encoding-lengths.


I've seen this approach used in an assembler for Transputers, where
one has to use an additional prefix op-code for every 4 bits encoding
the branch distance. Using the optimistic approach really made a
difference.


The more general problem of minimizing program length with arbitrary
expressions using code-labels probably is NP-complete. Some of these
expressions might actually get smaller if one elongates some other
instruction. --- Positive sums of code-snippet-lengths, as in the
variable length branch problem, can only get bigger if the size of
some instructions is increased.


Christian.

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