Span-Dependent Instruction Bibliography

Here's a list of what I found on my 40-foot shelf. Entries for the articles
I actually have rather than just have pointers to are annotated.


D. L. Richards, "How to keep the addresses short," CACM 14:5, pp. 346-349,
May 1971.


Wulf, William, et al., The Design of an Optimizing Compiler, Elsevier, 1975.


The famous book on the Bliss-11 compiler. Touches on branch
chaining and branch optimization on pp. 118-119. Out of print.


Gideon Frieder and Harry J. Saal, "A process for the determination of
addresses in variable length addressing," CACM 19:6, pp 335-338, Jun 76.


Describes an APL implementation that uses either matrix inversion
or integer programming.


Thomas G. Szymanski, "Assembling Code for Machines with Span-Dependent
Instructions", CACM 21:4, pp. 300-308, April 1978.


Describes the branch shrinking approach used in Unix assemblers,
an optimal two-pass algorithm which is more effective and in most
cases faster than the shrinking approach, and a proof that
minimizing program length is NP complete.


M. H. Williams, "Long/short address optimization in assemblers," Software
Practice and Experience 9, pp. 227-235, 1979.


Edward L. Robertson, "Code generation and storage allocation for machines
with span-dependent instructions," TOPLAS 1:1, pp. 71-83, Jul 1979.


Describes an algorithm similar to Szymanski's and considers the
possibility of rearranging code to minimize the number of long
branches, which also turns out to be NP-complete.


Bruce Leverett and Thomas G. Szymanski, "Chaining span-dependent jump
instructions," TOPLAS 2:3, pp. 274-289, Jul 1980.


Introduces a theory of branch chaining, shows that perfect chaining
is also NP-complete, but a decent approximation is n^2.


I didn't see any references after 1980. Either I've missed them or there's
nothing more to be said.


John Levine, comp.compilers moderator
johnl@iecc.cambridge.ma.us or {spdcc|ima|world}!iecc!johnl
[John Limpert <gronk!johnl@uunet.UU.NET> also sent in a pointer to Szymanski's
first article.]


--

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