Re: Vax span-dependent jumps

Henry Spenser writes...


>Our moderator writes:
>>[... I wrote the original AIX assembler for the RT PC, another machine with
>>span-dependent jumps, by mutating the System III Vax assembler. The code to
>>do span-dependent jumps was pretty straightforward, in pass 1 it assumed
>>they'd all be the long form and made a table of all of them, then between
>>passes 1 and 2 iterated over that table looking for branches that could be
>>converted to the short form...
>
>General comment: this is theoretically the wrong approach, since there are
>sequences where the decisions interact so that branch X can be short only
>if branch Y is also short, and a one-at-a-time algorithm that starts with
>all of them long won't shorten them.


Actually, the algorithm that Bliss uses is exactly the
opposite. The assumption is that ALL span-dependent
instructions [SDI's] will be short. For each SDI, two span
values are calculated:


- one assuming that all intervening SDI's are resolved
to their smallest size. [Call this the MIN]


- the other assuming that all SDI's are resolved long.
[Call this the MAX]


Then you just iterate over the list of SDIs, and consider the
three cases:


1. The MIN and MAX are both small enough to reach with
the short form instruction. [Resolve this SDI as
short and adjust all intervening SDI MAXs down]


2. The MIN and the MAX are both larger than the short
form. [ Resolve this SDI as long and adjust all
intervening SDI MINs up]


3. The MIN is small enough, but the MAX is larger than
the short form would allow. [Wait for more
information]


If at the end of an iteration, you have not found any
candidates for case 1 or 2, then you are in a mutual
dependency situation in which if all intervening SDIs were
resolved short, then each SDI could be resolved short. So,
just resolve the rest of the SDIs as short.


In the worst case, this algorithm could converge very slowly.
In practice (measured on Bliss-32 and Bliss-16) it terminated
after 3 or fewer iterations.


(Of course, the Bliss-32 algorithm was actually more complex,
as it combined 3 different possible lengths AND the ability to
branch chain as well. Back when B32 was written, memory was
still more important than speed [remember, the 11/780 was
supposed to be able to run with ONLY 256KB!!!!], so you could
choose to optimize for space at the expense of the speed of
branching to a branch.)


There are several papers on SDI and branch-chaining in the first 2
volumes of TOPLAS.
[See the next message for a short bibliography. -John]
--

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