Re: Span-Dependent Instruction Bibliography

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
--

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