Path: utzoo!utgpu!news-server.csri.toronto.edu!cs.utexas.edu!sdd.hp.com!spool2.mu.edu!uunet!world!iecc!compilers-sender
From: norman@parc.xerox.com (Norman Adams)
Newsgroups: comp.compilers
Subject: Re: Span-Dependent Instruction Bibliography
Keywords: assembler, optimize, code
Message-ID: <91Jan3.113209pst.3137@crevenia.parc.xerox.com>
Date: 3 Jan 91 19:31:57 GMT
References: <9101022304.AA22609@iecc.cambridge.ma.us>
Sender: compilers-sender@iecc.cambridge.ma.us
Reply-To: Norman Adams <norman@parc.xerox.com>
Organization: Compilers Central
Lines: 42
Approved: compilers@iecc.cambridge.ma.us

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.