Re: Span-Dependent Instruction Bibliography

Norman Adams <>
Thu, 3 Jan 1991 11:31:57 PST

          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: Norman Adams <>
Keywords: assembler, optimize, code
Organization: Compilers Central
References: <>
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
extended abstract:

    Michael J. Fischer (Yale Univ), Micheal S. Paterson (Univ. of Warwick)
    "Dynamic Monotone Priorities on Planar Sets (extended abstract)"
    April 30, 1985

Post a followup to this message

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