johnl@iecc.cambridge.ma.us (John R. Levine) (01/03/91)
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.]
--
Send compilers articles to compilers@iecc.cambridge.ma.us or
{ima | spdcc | world}!iecc!compilers. Meta-mail to compilers-request.preston@libya.rice.edu (Preston Briggs) (01/03/91)
John R. Levine <johnl@iecc.cambridge.ma.us> writes: >Here's a list of what I found on my 40-foot shelf. ... Another related paper is Jump minimization in linear-time Ramanath and Solomon TOPLAS 6(4), October 1984 It's more compiler-oriented (vs. assembler). Arranges basic blocks to minimize the number of unconditional jumps. Fast and optimimal for "structured" programs (reducible flow graphs?). They also show the problem is NP-Complete for unstructured code (though their algorithm still does a reasonable job). Has anyone ever measured the efficacy of any of these algorithms? An interesting study might examine the effectiveness of 2 or more of the assembler-oriented improvers versus the above paper on machines like the VAX or 680x0 and some currently interesting RISC machine. A nice test case would be the SPEC benchmarks, either the C or Fortran programs. Preston Briggs [Szymanski's papers have some effectiveness results. His first paper reports that in some pile of PDP-11 code, his algorithm shortened considerably more branches than the one the assembler used. -John] -- Send compilers articles to compilers@iecc.cambridge.ma.us or {ima | spdcc | world}!iecc!compilers. Meta-mail to compilers-request.
norman@parc.xerox.com (Norman Adams) (01/04/91)
John Levine, comp.compilers moderator, writes:
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.
Span dependent branches are a restricted form of span-dependent
assembly expressions. Szymanski proves that minimizing arbitrary
span-dependent assembly expressions is NP-complete.
When faced with the task of writing a span-dependent branch minimizer
for the T assembler, I consulted a nearby theory powerhouse, Mike
Fischer. He said that nothing better than relaxation (Szymanski's
algorithm) was obvious, but "surely there is a better way." A few
years later, I got a paper from him in the mail. From that paper:
It is easy to see that a minimal size program can be obtained by
starting with all jumps short and traversing the program
repeatedly, converting short jumps to long on each pass as
necessary. A straightforward implementation of this strategy
however is quite ineffient since up to O(n) passes may be required
for a program containing n jumps [ each pass being O(n) ].
...
Using a monotonic priority set, we obtain an algorithm for optimal
assembly of jumps that runs in time O(n log n), independent of S
[ S is the maximum short jump distance ].
...
I assume the paper got published somewhere, but all I have is the
extended abstract:
Michael J. Fischer (Yale Univ), Micheal S. Paterson (Univ. of Warwick)
"Dynamic Monotone Priorities on Planar Sets (extended abstract)"
April 30, 1985
--
Send compilers articles to compilers@iecc.cambridge.ma.us or
{ima | spdcc | world}!iecc!compilers. Meta-mail to compilers-request.