Path: utzoo!utgpu!news-server.csri.toronto.edu!cs.utexas.edu!yale!mintaka!spdcc!iecc!compilers-sender From: preston@libya.rice.edu (Preston Briggs) Newsgroups: comp.compilers Subject: Re: Span-Dependent Instruction Bibliography Keywords: assembler, optimize, bibliography Message-ID: <1991Jan3.060915.3641@rice.edu> Date: 3 Jan 91 06:09:15 GMT References: <9101022304.AA22609@iecc.cambridge.ma.us> Sender: compilers-sender@iecc.cambridge.ma.us Reply-To: preston@libya.rice.edu (Preston Briggs) Organization: Rice University, Houston Lines: 29 Approved: compilers@iecc.cambridge.ma.us John R. Levine writes: >Here's a list of what I found on my 40-foot shelf. ... Another related paper is Jump minimization in linear-time Ramanath and Solomon TOPLAS 6(4), October 1984 It's more compiler-oriented (vs. assembler). Arranges basic blocks to minimize the number of unconditional jumps. Fast and optimimal for "structured" programs (reducible flow graphs?). They also show the problem is NP-Complete for unstructured code (though their algorithm still does a reasonable job). Has anyone ever measured the efficacy of any of these algorithms? An interesting study might examine the effectiveness of 2 or more of the assembler-oriented improvers versus the above paper on machines like the VAX or 680x0 and some currently interesting RISC machine. A nice test case would be the SPEC benchmarks, either the C or Fortran programs. Preston Briggs [Szymanski's papers have some effectiveness results. His first paper reports that in some pile of PDP-11 code, his algorithm shortened considerably more branches than the one the assembler used. -John] -- Send compilers articles to compilers@iecc.cambridge.ma.us or {ima | spdcc | world}!iecc!compilers. Meta-mail to compilers-request.