2 Jan 91 15:30:51 GMT

Related articles |
---|

Vax span-dependent jumps chris@mimsy.umd.edu (1990-12-23) |

Re: Vax span-dependent jumps henry@zoo.toronto.edu (1990-12-30) |

Re: Vax span-dependent jumps lehotsky@aries.osf.org (1991-01-02) |

Re: Vax span-dependent jumps ccplumb@spurge.uwaterloo.ca (1991-01-03) |

Newsgroups: | comp.compilers |

From: | lehotsky@aries.osf.org (Alan Lehotsky) |

Keywords: | optimize, code, assembler |

Organization: | Open Software Foundation |

References: | <9012111913.AA07310@cs-sun-fsa.cpsc.ucalgary.ca> <14692@goofy.megatest.UUCP> <28765@mimsy.umd.edu> <1990Dec30.005507.7842@zoo.toronto.edu> |

Date: | 2 Jan 91 15:30:51 GMT |

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]

--

Post a followup to this message

Return to the
comp.compilers page.

Search the
comp.compilers archives again.