|Span-Dependent Instruction Bibliography email@example.com (John R. Levine) (1991-01-02)|
|Re: Span-Dependent Instruction Bibliography firstname.lastname@example.org (1991-01-03)|
|Re: Span-Dependent Instruction Bibliography email@example.com (Norman Adams) (1991-01-03)|
|Re: Span-Dependent Instruction Bibliography markz@ssc.UUCP (1991-01-04)|
|From:||Norman Adams <firstname.lastname@example.org>|
|Keywords:||assembler, optimize, code|
|Date:||Thu, 3 Jan 1991 11:31:57 PST|
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
Michael J. Fischer (Yale Univ), Micheal S. Paterson (Univ. of Warwick)
"Dynamic Monotone Priorities on Planar Sets (extended abstract)"
April 30, 1985
Return to the
Search the comp.compilers archives again.