Span-Dependent Instruction Bibliography

John R. Levine <>
Wed, 2 Jan 91 23:04:44 EST

          From comp.compilers

Related articles
Span-Dependent Instruction Bibliography (John R. Levine) (1991-01-02)
Re: Span-Dependent Instruction Bibliography (1991-01-03)
Re: Span-Dependent Instruction Bibliography (Norman Adams) (1991-01-03)
Re: Span-Dependent Instruction Bibliography markz@ssc.UUCP (1991-01-04)
| List of all articles for this month |

Newsgroups: comp.compilers
From: John R. Levine <>
Keywords: assembler, optimize, bibliography
Organization: Compilers Central
Date: Wed, 2 Jan 91 23:04:44 EST

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 or {spdcc|ima|world}!iecc!johnl
[John Limpert <gronk!johnl@uunet.UU.NET> also sent in a pointer to Szymanski's
first article.]


Post a followup to this message

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