Path: utzoo!utgpu!news-server.csri.toronto.edu!cs.utexas.edu!uunet!world!iecc!compilers-sender From: johnl@iecc.cambridge.ma.us (John R. Levine) Newsgroups: comp.compilers Subject: Span-Dependent Instruction Bibliography Keywords: assembler, optimize, bibliography Message-ID: <9101022304.AA22609@iecc.cambridge.ma.us> Date: 3 Jan 91 04:04:44 GMT Sender: compilers-sender@iecc.cambridge.ma.us Reply-To: John R. Levine Organization: Compilers Central Lines: 52 Approved: compilers@iecc.cambridge.ma.us 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 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.